\section{Introduction}
A special scheduling problem comes with the problem of data dissemination to mobile sinks. In the base station--mobile host model, data sources deliver the data to certain base stations as needed, when the mobile host moves into the range of one of the base stations, it retrieves the data. We could assume the bandwidth from the sources to the base stations is infinite so that the retrieval is only restrained by the time windows when mobile hosts connect to the base station.

This scheduling problem differs from other scheduling problems in which deadline for each data item appears machine-dependent. This is because as mobile sinks travel, they meet different base stations at different time.

To denote the scheduling problems we use the three-field notation $\alpha|\beta|\gamma$ introduced by Graham \cite{graham1979oaa}. $\alpha$ specifies the machine environment, $\beta$ specifies the job characteristics and $\gamma$ denotes the optimality criterion. There are $n$ jobs: $J_1,...,J_n$ and $m$ machines: $M_1,...,M_m$. For each job $J_j$, let $p_j$ to denote the processing time, $r_j$ and $d_j$ to denote the release and due time, and $w_j$ to denote the weight of $J_j$. A schedule is for each job an allocation of one or more time intervals to one or more machines.

We focus on the objective that maximize the total profit of a schedule, or minimize the weighted sum of penalty (lateness). We use the objective function $\sum w_j U_j$ (weighted sum of 0--1 penalty functions \cite{graham1979oaa}) in our problems.

Think the retrieval of data from base stations as jobs and base stations as machines, the time when mobile sinks connect to the base stations as the release time and the time when mobile sinks lose this connection as deadline. The problem can be written as:
\[
Pm~\vert r_{ij},~d_{ij}~\vert \sum w_jU_j
\]

A better studied problem with $r_{ij}=0$ and uniform deadlines $d_{ij}=d_j$ can be written as:
\[
Pm~\vert~\vert \sum w_jU_j
\]

One even simpler version of this problem is that each job has unit processing time ($p_j=1$). We can prove that it is polynomially solvable as a matching problem.

The problem is $\mathcal{NP}$--hard because the problem
\[
1~\vert~\vert \sum w_jU_j
\]
is proved by Karp \cite{karp1972rac} to be $\mathcal{NP}$--hard in ordinary sense that can be simplified from our problem by allowing only one machine and $r_j=0$.

